Fiches de Révision Détaillées : NSI Première

1.1 - Entier dans une base b

Principes

• Un nombre est représenté dans une base b (avec b ≥ 2) à l'aide de b chiffres de 0 à b-1.
• Bases courantes : binaire (base 2, chiffres 0-1), décimale (base 10, chiffres 0-9), hexadécimale (base 16, chiffres 0-9 puis A=10, B=11, ..., F=15).
• Conversion base b vers base 10 : On décompose le nombre en puissances de la base b.
  • Ex: $1A5_{16} = 1 \times 16^2 + 10 \times 16^1 + 5 \times 16^0 = 256 + 160 + 5 = 421_{10}$
  • Ex: $1101_2 = 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 8 + 4 + 0 + 1 = 13_{10}$
• Conversion base 10 vers base b : On utilise la méthode des divisions successives par b et on lit les restes de bas en haut.
  • Ex: Convertir 456 en binaire :
    $456 \div 2 = 228$ reste 0
    $228 \div 2 = 114$ reste 0
    $114 \div 2 = 57$ reste 0
    $57 \div 2 = 28$ reste 1
    ... jusqu'à un quotient de 0. On lit les restes en remontant : $111001000_2$.

Nombre de bits 🖥️

• Avec n bits, on peut coder $2^n$ entiers différents (de 0 à $2^n-1$). Par exemple, sur 8 bits (1 octet), on peut représenter $2^8 = 256$ valeurs, de 0 à 255.
• Pour coder un entier k, il faut au moins n bits tel que $2^{n-1} \le k < 2^n$.
• La somme de deux entiers codés sur n bits nécessite au plus n+1 bits.
• Le produit de deux entiers codés sur n bits nécessite au plus 2n bits.

1.2 - Binaire d'un entier relatif : Complément à 2

Principe

Le complément à 2 est la méthode standard pour représenter les entiers relatifs. Le bit de poids fort (le plus à gauche) indique le signe (0 pour positif, 1 for négatif).

Conversion d'un nombre négatif en complément à 2 (sur n bits)

1. Prendre la valeur absolue du nombre.
2. La convertir en binaire sur n bits (en complétant avec des 0 à gauche si besoin).
3. Inverser tous les bits (les 0 deviennent des 1 et vice-versa). C'est le complément à 1.
4. Ajouter 1 au résultat.

Exemple pour -5 sur 4 bits : 5 $\rightarrow$ 0101 $\rightarrow$ (inversion) 1010 $\rightarrow$ (ajout de 1) 1011. Donc $(-5)_{10} = (1011)_2$.

Conversion inverse (d'un nombre négatif en complément à 2 vers le décimal)

1. Inverser tous les bits.
2. Ajouter 1.
3. Convertir le résultat binaire en décimal.
4. Ajouter le signe "-".

Exemple pour 1011 sur 4 bits : 1011 $\rightarrow$ (inversion) 0100 $\rightarrow$ (ajout de 1) 0101. $(0101)_2 = 5_{10}$. Le nombre est donc -5.

1.3 - Nombres réels : Nombres à virgule flottante

Principe

La représentation des nombres réels en machine est souvent une approximation. Un nombre binaire à virgule se décompose avec des puissances de 2, y compris négatives pour la partie fractionnaire.

• Exemple : $10.101_2 = 1 \times 2^1 + 0 \times 2^0 + 1 \times 2^{-1} + 0 \times 2^{-2} + 1 \times 2^{-3} = 2 + 0.5 + 0.125 = 2.625_{10}$

Problème de précision ⚠️

Certains nombres décimaux à développement fini n'ont pas de représentation binaire finie (ex: $0.1_{10} = 0.000110011..._2$). Cela mène à des erreurs d'arrondi inévitables.

>>> 0.1 + 0.2
0.30000000000000004

Recommandation : Pour comparer deux flottants `a` et `b`, on ne teste jamais `a == b`. On vérifie si leur différence est inférieure à une petite marge d'erreur (epsilon) : `abs(a - b) < epsilon`.

Virgule flottante

Un nombre est décomposé en 3 parties (norme IEEE-754) : signe (1 bit), exposant (décale la virgule) et mantisse (les chiffres significatifs). Cela permet de représenter des nombres très grands ou très petits.

1.4 - Expressions booléennes

Valeurs et Opérateurs

• Un booléen ne peut prendre que deux valeurs : Vrai (True / 1) ou Faux (False / 0).
• Opérateurs principaux et leurs tables de vérité :
  • NOT (non) : Inverse la valeur. `NOT 1 -> 0`.
  • AND (et) : Vrai (1) seulement si les deux opérandes sont vraies. `1 AND 1 -> 1`, sinon 0.
  • OR (ou) : Vrai (1) si au moins une des deux opérandes est vraie. `0 OR 0 -> 0`, sinon 1.
  • XOR (ou exclusif) : Vrai (1) si les deux opérandes sont différentes. `1 XOR 0 -> 1`, `0 XOR 1 -> 1`.

Propriétés (Algèbre de Boole)

• Distributivité : `A AND (B OR C) = (A AND B) OR (A AND C)`
• Lois de De Morgan : `NOT (A AND B) = (NOT A) OR (NOT B)` et `NOT (A OR B) = (NOT A) AND (NOT B)`

1.5 - Encodage des caractères : ASCII, ISO, Unicode

Principe

Un ordinateur ne manipulant que des nombres, chaque caractère (lettre, symbole, etc.) doit être associé à un nombre unique. C'est le rôle de la table d'encodage.

• ASCII : Sur 7 bits (128 caractères). Comprend les lettres non accentuées, chiffres et symboles courants. Parfait pour l'anglais mais insuffisant pour les autres langues.
• ISO-8859-1 (Latin-1) : Sur 8 bits (1 octet, 256 caractères). C'est une extension de l'ASCII qui inclut les caractères accentués des langues d'Europe de l'Ouest.
• Unicode (UTF-8) : Standard universel qui vise à couvrir tous les caractères de toutes les langues du monde (plus de 140 000 caractères). UTF-8 est l'implémentation la plus courante. Il utilise un nombre variable d'octets par caractère et est rétrocompatible avec l'ASCII. C'est l'encodage par défaut sur le web. 🌐

2.1 & 2.3 - p-uplets (Tuples) et Dictionnaires

p-uplets (Tuples en Python)

• Définition : Une collection ordonnée et non modifiable (immuable) d'éléments.
• Syntaxe Python : coordonnees = (10.5, 4.2)
• Caractéristiques :
  • L'ordre des éléments est préservé.
  • Une fois créé, un tuple ne peut plus être modifié (pas d'ajout, de suppression ou de changement d'élément).
• Usage : Idéal pour les données qui ne doivent pas changer, comme des coordonnées de points. Une fonction peut retourner un tuple pour renvoyer plusieurs valeurs.

  def division_euclidienne(a, b):
      quotient = a // b
      reste = a % b
      return (quotient, reste) # Retourne un tuple
  
  q, r = division_euclidienne(10, 3) # q=3, r=1

Dictionnaires

• Définition : Une collection de paires clé-valeur. Les clés sont uniques et servent à accéder aux valeurs correspondantes.
• Syntaxe Python : personne = {"nom": "Alice", "age": 25}
• Opérations courantes :
  • Accès à une valeur : personne["age"] renvoie `25`.
  • Ajout/Modification : personne["ville"] = "Paris"
  • Itération sur les paires clé-valeur :

    for cle, valeur in personne.items():
        print(f"{cle}: {valeur}")

2.2 - Tableaux (Listes en Python)

Caractéristiques

• Définition : Une collection ordonnée et modifiable (mutable) d'éléments.
• Indexation : Chaque élément est accessible par son index (position), qui commence à 0. tableau[0] est le premier élément, `tableau[-1]` est le dernier.
• Opérations courantes :
  • Modification : tableau[1] = "nouvelle_valeur".
  • Ajout à la fin : tableau.append("dernier").
  • Suppression : tableau.pop(2) (supprime l'élément à l'index 2).

Création et Matrices

• En compréhension : Syntaxe concise et efficace pour créer des listes.
  • Exemple (liste des 10 premiers carrés) : carres = [i*i for i in range(10)]
• Matrices (Tableau de tableaux) : Une liste de listes permet de représenter une grille ou une matrice.
  • Exemple : matrice = [[1, 2], [3, 4]]
  • Accès : matrice[ligne][colonne]. Ainsi, matrice[1][0] vaut `3`.

7.1 - Parcours Séquentiel

Le parcours séquentiel consiste à examiner chaque élément d'une structure de données (comme un tableau) l'un après l'autre, du début à la fin. C'est l'approche la plus simple mais elle est fondamentale.

Recherche d'une occurrence

Recherche l'index de la première apparition d'une valeur dans un tableau.

def recherche_occurrence(tableau, valeur):
    for i in range(len(tableau)):
        if tableau[i] == valeur:
            return i  # Retourne l'index si la valeur est trouvée
    return -1  # Convention pour indiquer que la valeur n'est pas dans le tableau

Recherche d'un extremum (minimum et maximum)

def recherche_extremum(tableau):
    if not tableau:  # Cas d'un tableau vide
        return (None, None)
    
    minimum = tableau[0]
    maximum = tableau[0]

    for element in tableau:
        if element < minimum:
            minimum = element
        if element > maximum:
            maximum = element

    return (minimum, maximum)

Calcul d'une moyenne

def calcul_moyenne(tableau):
    if not tableau:
        return 0
        
    somme = 0
    for element in tableau:
        somme += element
    
    return somme / len(tableau)

7.2 - Tris par insertion et par sélection

Le but du tri est d'organiser les éléments d'un tableau dans un ordre spécifique (généralement croissant).

Tri par sélection

Principe : On trouve le plus petit élément du tableau non trié et on l'échange avec l'élément au début de la partie non triée. On répète l'opération jusqu'à ce que tout le tableau soit trié.

def tri_selection(tableau):
    n = len(tableau)
    for i in range(n):
        # Trouver le minimum dans la partie non triée tableau[i..n-1]
        min_idx = i
        for j in range(i + 1, n):
            if tableau[j] < tableau[min_idx]:
                min_idx = j
        
        # Échanger le minimum trouvé avec le premier élément
        tableau[i], tableau[min_idx] = tableau[min_idx], tableau[i]
    return tableau

Tri par insertion

Principe : On parcourt le tableau et pour chaque élément, on l'insère à sa place correcte dans la partie déjà triée (qui se trouve à sa gauche).

def tri_insertion(tableau):
    for i in range(1, len(tableau)):
        cle = tableau[i]
        j = i - 1
        # Déplacer les éléments de tableau[0..i-1] qui sont plus grands que la clé
        # vers une position à droite de leur position actuelle
        while j >= 0 and cle < tableau[j]:
            tableau[j + 1] = tableau[j]
            j -= 1
        tableau[j + 1] = cle
    return tableau

7.3 - Algorithme des k plus proches voisins (k-NN)

Principe (Algorithme d'Apprentissage) 🧠

Pour classer un nouvel élément, on regarde ses k voisins les plus proches dans un jeu de données existant. Le nouvel élément se voit attribuer la classe la plus fréquente parmi ces k voisins.

1. Choisir k : Le nombre de voisins à considérer (par exemple, k=3).
2. Calculer les distances : Mesurer la distance (souvent euclidienne) entre le nouvel élément et tous les autres points.
3. Trouver les voisins : Identifier les k points ayant les plus petites distances.
4. Voter : Compter les classes des k voisins. La classe majoritaire l'emporte.

Programme Important

import math

def distance_euclidienne(point1, point2):
    # Suppose que les points sont des tuples/listes de coordonnées (x, y)
    return math.sqrt((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2)

def k_plus_proches_voisins(donnees, point_a_classer, k):
    distances = []
    for categorie, points_categorie in donnees.items():
        for point in points_categorie:
            dist = distance_euclidienne(point, point_a_classer)
            distances.append((dist, categorie))

    # Trier les distances par ordre croissant
    distances.sort(key=lambda x: x[0])

    # Prendre les k premiers voisins
    voisins = distances[:k]

    # Compter les votes
    votes = {}
    for _, categorie in voisins:
        votes[categorie] = votes.get(categorie, 0) + 1
    
    # Retourner la catégorie avec le plus de votes
    return max(votes, key=votes.get)

7.4 - Recherche Dichotomique dans un tableau trié

Principe

C'est une méthode de recherche très efficace qui consiste à diviser récursivement par deux l'intervalle de recherche. On compare l'élément cherché avec l'élément central du tableau. Si ce n'est pas le bon, on sait si l'élément se trouve dans la moitié gauche ou droite, et on élimine l'autre moitié.

Programme Important

def recherche_dichotomique(tableau, valeur):
    debut = 0
    fin = len(tableau) - 1

    while debut <= fin:
        milieu = (debut + fin) // 2
        
        if tableau[milieu] == valeur:
            return milieu  # Trouvé !
        elif tableau[milieu] < valeur:
            debut = milieu + 1  # Chercher dans la moitié droite
        else: # tableau[milieu] > valeur
            fin = milieu - 1  # Chercher dans la moitié gauche
            
    return -1  # Non trouvé

7.5 - Algorithmes gloutons

Principe 💡

Un algorithme glouton (greedy algorithm) construit une solution à un problème étape par étape. À chaque étape, il fait le choix qui semble le meilleur localement, sans tenir compte des conséquences futures de ce choix.

• Avantage : Souvent simple à concevoir et rapide à exécuter.
• Inconvénient : Ne garantit pas de trouver la solution optimale globale. Il peut se retrouver piégé dans un optimum local.

Exemple : Rendu de monnaie 💶

Problème : Rendre une somme donnée avec le moins de pièces/billets possible. Stratégie gloutonne : Toujours donner la plus grande pièce/billet possible sans dépasser la somme restante.

def rendre_monnaie(montant_a_rendre, systeme_monetaire):
    # systeme_monetaire doit être trié par ordre décroissant
    # ex: [50, 20, 10, 5, 2, 1]
    
    rendu = {}
    for piece in systeme_monetaire:
        if montant_a_rendre >= piece:
            nombre_pieces = montant_a_rendre // piece
            rendu[piece] = nombre_pieces
            montant_a_rendre %= piece
            
    return rendu

# Pour le système euro, cette stratégie est optimale.
# Ce n'est pas vrai pour tous les systèmes monétaires !

Exemple : Problème du sac à dos (version simple)

Problème : Remplir un sac de capacité limitée avec des objets ayant chacun une valeur et un poids pour maximiser la valeur totale. Stratégie gloutonne (une parmi d'autres) : Trier les objets par rapport valeur/poids décroissant et prendre les meilleurs objets jusqu'à ce que le sac soit plein. Cette stratégie n'est pas toujours optimale pour le problème du sac à dos 0/1 (où on doit prendre ou laisser un objet entier).